mutable struct PerfectBipartiteMatchingLPSolver <: PerfectBipartiteMatchingSolver
  solver

  # Optimisation model (reused by solve_linear). 
  m # ::Model
  x # ::Matrix{Variable}

  function PerfectBipartiteMatchingLPSolver(solver)
    return new(solver, nothing, nothing)
  end
end

function build!(solver::PerfectBipartiteMatchingLPSolver, reward::Matrix{Distribution})
  n = size(reward, 1)

  # Build the optimisation model behind solve_linear. 
  solver.m = Model(solver=solver.solver)
  solver.x = @variable(solver.m, [1:n, 1:n], lowerbound=0, upperbound=1)
  for i in 1:n # Left nodes. 
    @constraint(solver.m, sum(solver.x[i, j] for j in 1:n) <= 1)
  end
  for j in 1:n # Right nodes. 
    @constraint(solver.m, sum(solver.x[i, j] for i in 1:n) <= 1)
  end
end

function solve_linear(solver::PerfectBipartiteMatchingLPSolver, weights::Dict{Tuple{Int, Int}, Float64})
  @objective(solver.m, Max, sum(weights[(i, j)] * solver.x[i, j] for (i, j) in keys(weights)))
  solve(solver.m)
  x = getvalue(solver.x)
  return [ind2sub(x, v) for v in find(x .>= .5)] # TODO: ind2sub deprecated in Julia 0.7. 
  # https://github.com/JuliaLang/julia/pull/24715#issuecomment-348323494
end
